The present invention relates to computer system and more particularly to managing memory for a runtime execution environment.
In a dynamic run-time environment for a language such as JAVA(trademark), memory management for objects is very important. In specific, a dynamic run-time environment has to handle the allocation and deallocation of memory for objects. An object is an entity that encapsulates data and, in some environments such as JAVA, operations associated with the object.
When an object is created, a certain amount of memory must be allocated for the object. When the object is no longer needed, the memory for the object needs to be deallocated so that it can be reused for other purposes. Memory deallocation can be manual, as in the C programming languages, or handled automatically by a xe2x80x9cgarbage collector.xe2x80x9d There are various types of garbage collectors. For example, a generational garbage collector distinguishes objects based on their lifetime because a recently-allocated object is usually a short-lived object. In one implementation of a generational garbage collector, objects are stored in one of at least two memory areas, referred to as xe2x80x9coldspacexe2x80x9d and xe2x80x9cnewspace.xe2x80x9d When an object is first created, memory for the object is allocated out the newspace. After the object has lasted for a period time, such as four scavenges of newspace, it is xe2x80x9ctenuredxe2x80x9d and migrated into the oldspace.
Use of different memory areas for objects, where the different areas are distinguished by the lifetime of the objects contained therein, allows the generational garbage collector to employ different allocation and garbage collection strategies for the memory areas. For example, since newspace tends to hold many objects that are frequently allocated and abandoned, memory allocation within newspace is preferably implemented by a cheap technique such as xe2x80x9cfrontier consingxe2x80x9d (incrementing a pointer to the beginning of free storage) and garbage collection by a copying garbage collector. On the other hand, since oldspace tends to hold fewer and longer-lived objects, it may be preferable to perform memory allocation a buddy or best fit allocation technique, and deallocation by a mark-sweep garbage collector.
The performance of a generational garbage collector is greatly affected by the efficiency of calculating a xe2x80x9croot setxe2x80x9d for all the objects in newspace. A root set for newspace is a set of objects such that the transitive closure of the set contains all the live objects in newspace. In specific, it is important to determine all the oldspace objects that reference objects in newspace. One method of simplifying the root set calculation is to maintain a xe2x80x9cremember table,xe2x80x9d which is a data structure used by the garbage collector to record which objects in newspace are referenced by an object in oldspace. The remember table is updated when an assignment operation might places a reference to a newspace object in an oldspace object. The check that occurs to determine whether an assignment operation places a reference to a newspace object in an oldspace object is referred to as a xe2x80x9cwrite barrierxe2x80x9d. It is desirable to detect such assignments in an efficient manner.
One approach to detecting the assignment of a reference to a newspace object in an oldspace object is to reserve a respective, contiguous range of memory locations for newspace and oldspace, and to examine the location of the objects with respect to the reserved ranges. For example, if newspace objects are always allocated in the contiguous range 012,000,000-012,777,777 (octal) and oldspace objects are always allocated in the contiguous range 023,450,000-023,517,730, then an occurrence of storing of a newspace reference into an oldspace object can be identified simply by comparing the location of the objects within the reserved ranges. Thus, a reference to one object at location 012,345,670 is determined to be in newspace because the location 012,345,670 falls within the range 012,000,000-012,777,777.
Many run-time environments, however, are implemented in an environment that does not allow for large contiguous memory areas to be allocated. In such environments, memory can only be obtained as a plurality of usually segments. As a result, determining which memory area the object is located in cannot merely be determined by examining the location of the object.
One approach to determining to which memory area an object belongs involves traversing an ancillary data structure that lists which segments are allocated to which memory area. However, this approach incurs many expensive pointer dereferences for the ancillary data structure. Another approach involves storing a header at the beginning of every object that describes the space within which the object is located. Accessing the information stored in the object header, however, requires dereferencing a memory pointer to the object, which is expensive due to holes in the instruction pipeline, cache misses, or even a page fault if the page upon which the object header is located has been swapped out by the virtual memory system.
Therefore, a need exists for a run-time environment to manage storage properties for objects, such as properties that indicate within which memory area an object is allocated. There also exists a need for efficiently determining a storage property for an object, preferably without having to dereference a memory pointer. Furthermore, there is a need for an efficient way to detect an assignment of a reference to a newspace object within an oldspace object.
These and other needs are addressed by encoding storage properties about an object within some of the least significant bits, called a xe2x80x9ctag,xe2x80x9d of a reference to the object, such as a machine pointer. Therefore, the storage properties can be efficiently determined simply by extracting and examining the specified bits of the tag without having to dereference the machine pointer. The storage properties of an object that can be encoded in the tag of a reference to the object generally indicate how and when the object is stored in memory managed by a run-time environment. For example, the tag can encode information about the lifetime, format, and/or contiguity of an object; thus, the tag can indicate whether the object is allocated in newspace or in oldspace.
Accordingly, one aspect of the invention relates to a computer-implemented method and computer-readable medium bearing instructions for managing information about a storage property for an object. The object is stored in a memory, for example at an N-bit aligned address, and a reference to the object is created by storing, in an base address portion of the reference, a location of the object within the memory. The methodology includes storing, in a tag portion of the reference, the information about the storage property for the object. The tag portion of the reference includes one or more bits of the reference that are less significant than bits for the address portion. In one embodiment, information about the storage property for the object is retrieved by accessing the tag portion of the reference to the object.
Another aspect of the invention pertains to a computer-implemented method and computer-readable medium bearing instructions for managing memory for a plurality of objects. The methodology includes allocating the objects in a first memory area and migrating some of the objects from the first memory area to a second memory area based on their lifetimes. Either the first memory area or the second memory area or both include a plurality of noncontiguous segments. A data structure of information about which second objects in the second memory area reference first objects in the first memory area is maintained by determining whether a first object is allocated in the first memory area and a second object is allocated in the second memory area based on a first reference to a first object and a second reference to a second object, without dereferencing a memory pointer. In one embodiment, determining the first object is allocated in the first memory area and the second object is allocated in the second memory area is performed by extracting the tags of the references to the first and second objects and comparing the tags.
Still other objects and advantages of the present invention will become readily apparent from the following detailed description, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.